package swordRefersOffer.p37;

import java.util.Stack;

/**
 * @author: trtan
 * @date: 2021-06-30 09:37
 **/
public class Codec {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.right = new TreeNode(3);
        node.right.left = new TreeNode(4);
        node.right.right = new TreeNode(5);
        String serialize = new Codec().serialize(node);
        System.out.println(serialize);
        TreeNode root = new Codec().deserialize(serialize);
        print(root);
    }
    public static void print(TreeNode root) {
        if (root == null) {
            System.out.print("null, ");
            return;
        }
        System.out.print(root.val + ", ");
        print(root.left);
        print(root.right);
    }
    public String serialize(TreeNode root) {
        StringBuffer s = new StringBuffer();
        dfs(root, s);
        return s.toString().substring(0, s.length() - 1);
    }

    /**
     * 先序遍历
     * @param root
     * @param s
     * @return void
     * @author trtan
     * @date 2021/6/30 11:06
     */
    void dfs(TreeNode root, StringBuffer s) {
        if (root == null) {
            s.append("#,");
            return;
        }
        s.append(root.val + ",");
        dfs(root.left, s);
        dfs(root.right, s);
    }

    // 全局变量记录解析到的位置
    static int i = 0;
    public TreeNode deserialize(String data) {
        String[] strings = data.split(",");
        if ("#".equals(strings[0])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        i = 1;
        buildTree(strings, root);
        return root;
    }

    /**
     * 先左后右
     * @param strings
     * @param root
     * @return void
     * @author trtan
     * @date 2021/6/30 11:07
     */
    void buildTree(String[] strings, TreeNode root) {
        if (i >= strings.length || root == null) {
            return;
        }
        if ("#".equals(strings[i])) {
            root.left = null;
        } else {
            root.left = new TreeNode(Integer.parseInt(strings[i]));
        }
        i++;
        buildTree(strings, root.left);
        if (i >= strings.length || "#".equals(strings[i])) {
            root.right = null;
        } else {
            root.right = new TreeNode(Integer.parseInt(strings[i]));
        }
        i++;
        buildTree(strings, root.right);
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
